package main

import (
	"fmt"
	"sort"
)

func main() {
	fourSum([]int{2,2,2,2,2}, 8)
}

//给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[
//b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
//
//
// 0 <= a, b, c, d < n
// a、b、c 和 d 互不相同
// nums[a] + nums[b] + nums[c] + nums[d] == target
//
//
// 你可以按 任意顺序 返回答案 。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
//
//
// 示例 2：
//
//
//输入：nums = [2,2,2,2,2], target = 8
//输出：[[2,2,2,2]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// -10⁹ <= nums[i] <= 10⁹
// -10⁹ <= target <= 10⁹
//
// Related Topics 数组 双指针 排序 👍 1104 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
func fourSum(nums []int, target int) [][]int {
	var result [][]int
	sort.Ints(nums)

	for a := 0; a < len(nums); a++ {
		if a > 0 && nums[a] == nums[a - 1] {
			continue
		}
		for b := a + 1; b < len(nums); b++ {
			if b > a + 1 && nums[b] == nums[b -1]	{
				continue
			}
			for c := b + 1; c < len(nums); c++ {
				if c > b + 1 && nums[c] == nums[c - 1]{
					continue
				}
				for d := len(nums) - 1; d > c; d-- {
					if d < len(nums) - 1 && nums[d] == nums[d + 1]{
						continue
					}
					if nums[a]+nums[b]+nums[c]+nums[d] < target {
						break
					}
					if c == d {
						break
					}
					if nums[a]+nums[b]+nums[c]+nums[d] == target {
						result = append(result, []int{nums[a], nums[b], nums[c], nums[d]})
						fmt.Println(a, b, c, d)
					}
				}
			}
		}
	}
	return result
}

//leetcode submit region end(Prohibit modification and deletion)
